home *** CD-ROM | disk | FTP | other *** search
/ MPEG Toolkit / MPEG Toolkit.iso / dos / secmpeg3 / huff.c < prev    next >
C/C++ Source or Header  |  1997-01-01  |  7KB  |  332 lines
  1.  
  2. /* --- C ---
  3. ************************************************************************
  4. *
  5. *    Filename    : huff.c
  6. *    Description : Huffman-decoding
  7. *    Part of     : SECMPEG
  8. *
  9. *    Version     : 1.0
  10. *    Language    : C
  11. *    For machine : SunOS 4.1.x, INTERACTIVE Unix 2.2.1, Linux, MS-DOS
  12. *    Compile as  : see Makefile
  13. *
  14. *    Authors     : Juergen Meyer, Frank Gadegast
  15. *    Contact     : jm@cs.tu-berlin.de, phade@cs.tu-berlin.de
  16. *
  17. ************************************************************************
  18. */
  19.  
  20. #include "defs.h"
  21. #include <stdio.h>
  22. #include <stdlib.h>
  23. #ifdef DOS
  24. #ifdef GNU
  25.   #include <malloc.h>
  26. #else
  27.   #include <alloc.h>
  28. #endif
  29. #else
  30.   #include <malloc.h>
  31. #endif
  32. #include "huff.h"
  33.  
  34. /* ------ DEFINES ------ */
  35.  
  36. #define GetLeft(sval,huff) (((huff->state[(sval)]) >> 16)& 0x0000ffff)
  37. #define GetRight(sval,huff) ((huff->state[(sval)]) & 0xffff)
  38.  
  39. #define SetLeft(number,sval,huff) huff->state[(sval)]=\
  40.   (((huff->state[(sval)]) & 0xffff)|(number<<16));
  41. #define SetRight(number,sval,huff) huff->state[(sval)]=\
  42.   (((huff->state[(sval)]) & 0xffff0000)|(number));
  43.  
  44. #define EmptyState 0xffff  
  45. #define Numberp(value) ((value & 0x8000) ? 1 : 0)
  46. #define MakeHVal(value) (value | 0x8000)
  47. #define GetHVal(value) (value & 0x7fff)
  48.  
  49. /* ------ PUBLIC ------ */
  50.  
  51. int     InitHuffman();
  52. void    FreeHuffTables();
  53. INT     Decode(DHUFF *);
  54.  
  55.  
  56. /* ------ PRIVAT ------ */
  57.  
  58. static DHUFF *MakeDhuff();
  59. static void   LoadDTable();
  60. static INT    GetNextState();
  61. static void   AddCode(INT,INT,INT,DHUFF *);
  62.  
  63. /* ------ IMPORT ------ */
  64. extern int _GetBit();             /* decode.c */
  65.  
  66.  
  67. INT huffmantable_count;
  68.  
  69. extern INT Loud;
  70. extern INT ErrorValue;
  71. extern INT FrameInterval;
  72.  
  73.  
  74.  
  75. INT NumberBitsCoded=0;
  76.  
  77. DHUFF *MBADHuff            = NULL;
  78. DHUFF *MVDDHuff            = NULL;
  79. DHUFF *CBPDHuff            = NULL;
  80. DHUFF *T1DHuff             = NULL;
  81. DHUFF *T2DHuff             = NULL;
  82. DHUFF *IntraDHuff          = NULL;
  83. DHUFF *PredictedDHuff      = NULL;
  84. DHUFF *InterpolatedDHuff   = NULL;
  85. DHUFF *DCLumDHuff          = NULL;
  86. DHUFF *DCChromDHuff        = NULL;
  87. DHUFF **ModuloDHuff        = NULL;
  88. INT   **MyCoef             = NULL;
  89.  
  90. int    InitHuffman()
  91. {
  92.  
  93.  
  94.     INT i,j,count,largest,smallest,size;
  95.     
  96.  
  97. #ifdef DEBUG
  98.   fprintf(stderr,"%s : %d\n","init huffmann tables",huffmantable_count++);
  99. #endif
  100.  
  101.   MBADHuff = MakeDhuff();
  102.   MVDDHuff = MakeDhuff();
  103.   CBPDHuff = MakeDhuff();
  104.   T1DHuff = MakeDhuff();
  105.   T2DHuff = MakeDhuff();
  106.   IntraDHuff = MakeDhuff();
  107.   PredictedDHuff = MakeDhuff();
  108.   InterpolatedDHuff = MakeDhuff();
  109.   DCLumDHuff = MakeDhuff();
  110.   DCChromDHuff = MakeDhuff();
  111.  
  112.  
  113.   LoadDTable(MBACoeff,MBADHuff);
  114.   LoadDTable(MVDCoeff,MVDDHuff);
  115.   LoadDTable(CBPCoeff,CBPDHuff);
  116.   LoadDTable(TCoeff1,T1DHuff);
  117.   LoadDTable(TCoeff2,T2DHuff);
  118.   LoadDTable(IntraTypeCoeff,IntraDHuff);
  119.   LoadDTable(PredictedTypeCoeff,PredictedDHuff);
  120.   LoadDTable(InterpolatedTypeCoeff,InterpolatedDHuff);
  121.   LoadDTable(DCLumCoeff,DCLumDHuff);
  122.   LoadDTable(DCChromCoeff,DCChromDHuff);
  123.  
  124.  
  125.    return(TRUE);
  126. }
  127. void   FreeHuffTables()
  128. {
  129.        if(MBADHuff)          free(MBADHuff);
  130.        if(MVDDHuff)          free(MVDDHuff);
  131.        if(CBPDHuff)          free(CBPDHuff);
  132.        if(T1DHuff)           free(T1DHuff);
  133.        if(T2DHuff)           free(T2DHuff);
  134.        if(IntraDHuff)        free(IntraDHuff);
  135.        if(PredictedDHuff)    free(PredictedDHuff);
  136.        if(InterpolatedDHuff) free(InterpolatedDHuff);
  137.        if(DCLumDHuff)        free(DCLumDHuff);
  138.        if(DCChromDHuff)      free(DCChromDHuff);
  139.        if(ModuloDHuff)       free(ModuloDHuff);
  140.  
  141.        if(MyCoef)            free(MyCoef);
  142. }
  143.  
  144.  
  145. static DHUFF *MakeDhuff()
  146. {
  147.  
  148.   INT i;
  149.   DHUFF *temp = NULL;
  150.  
  151. #ifdef HUFF_DEBUG
  152.   fprintf(stderr,"%s\n","make decode-huffman structure");
  153. #endif
  154.  
  155.   temp = MakeStructure(DHUFF);
  156.   if(!temp) error_exit(ERROR_MEMORY);
  157.   temp->NumberStates=1;
  158.   for(i=0;i<512;i++) {temp->state[i] = -1;}
  159.   return(temp);
  160. }
  161.  
  162.  
  163. static void LoadDTable(INT *array,DHUFF *table)
  164. {
  165. #ifdef HUFF_DEBUG
  166.      fprintf(stderr,"%s\n","make decode-huffman table");
  167. #endif
  168.  
  169.   while(*array>=0)
  170.     {
  171.       AddCode(array[1],array[2],array[0],table);
  172.       array+=3;
  173.     }
  174. }
  175.  
  176.  
  177. static INT GetNextState(DHUFF *huff)
  178. {
  179.  
  180. #ifdef HUFF_DEBUG
  181.        fprintf(stderr," %s\n","get next state");
  182. #endif
  183.   if (huff->NumberStates==512)
  184.     {
  185.       fprintf(stderr,"Overflow\n");
  186.       error_exit(ERROR_BOUNDS);
  187.     }
  188.   return(huff->NumberStates++);
  189. }
  190.  
  191.  
  192. INT Decode(DHUFF *huff)
  193. {
  194.  
  195.   INT Next,cb;
  196.   INT CurrentState=0;
  197.  
  198.   while(TRUE)
  199.     {
  200.       cb = (INT)GetBit();
  201.       if (cb)
  202.     {
  203.       Next =  GetLeft(CurrentState,huff);
  204.       if (Next == EmptyState)
  205.       {
  206. #ifdef DEBUG
  207.           fprintf(stderr,"Invalid State Reached (decode).\n");
  208. #endif
  209.           error_exit(ERROR_BOUNDS);
  210.       }
  211.       else if (Numberp(Next))
  212.         return(GetHVal(Next));
  213.       else
  214.         CurrentState = Next;
  215.     }
  216.       else
  217.     {
  218.       Next =  GetRight(CurrentState,huff);
  219.       if (Next == EmptyState)
  220.       {
  221. #ifdef DEBUG
  222.           fprintf(stderr,"Invalid State Reached (decode).\n");
  223. #endif
  224.           error_exit(ERROR_BOUNDS);
  225.       }
  226.       else if (Numberp(Next))
  227.         return(GetHVal(Next));
  228.       else
  229.         CurrentState = Next;
  230.     }
  231.     }
  232. }
  233.  
  234. static void AddCode(INT n,INT code,INT value,DHUFF *huff)
  235. {
  236.   INT i,Next;
  237.   INT CurrentState=0;
  238.  
  239. #ifdef HUFF_DEBUG
  240.        fprintf(stderr," %s\n","add code");
  241.           fprintf(stderr,"Length: %d   Code: %d  Value: %d\n",
  242.              n,code,value);
  243. #endif
  244.  
  245.   if (value < 0)
  246.   {
  247. #ifdef HUFF_DEBUG
  248.       fprintf(stderr,"Negative addcode value: %d\n",value);
  249. #endif
  250.       error_exit(ERROR_BOUNDS);
  251.   }
  252.  
  253.   for(i=n-1;i>0;i--)
  254.     {
  255.       if (code & (1 << i))
  256.     {
  257.       Next = GetLeft(CurrentState,huff);
  258.       if (Next == EmptyState)
  259.         {
  260.           Next = GetNextState(huff);
  261.           SetLeft(Next,CurrentState,huff);
  262.           CurrentState = Next;
  263.         }
  264.       else if (Numberp(Next))
  265.         {
  266. #ifdef HUFF_DEBUG
  267.           fprintf(stderr,"Bad Value/State match (L) :\n");
  268.           fprintf(stderr,"Length: %d   Code: %d  Value: %d\n",
  269.              n,code,value);
  270. #endif
  271.           error_exit(ERROR_BOUNDS);
  272.         }
  273.       else
  274.         {
  275.           CurrentState = Next;
  276.         }
  277.     }
  278.       else
  279.     {
  280.       Next = GetRight(CurrentState,huff);
  281.       if (Next == EmptyState)
  282.         {
  283.           Next = GetNextState(huff);
  284.           SetRight(Next,CurrentState,huff);
  285.           CurrentState = Next;
  286.         }
  287.       else if (Numberp(Next))
  288.         {
  289. #ifdef HUFF_DEBUG
  290.           fprintf(stderr,"Bad Value/State match: (R) \n");
  291.           fprintf(stderr,"Length: %d   Code: %d  Value: %d\n",
  292.              n,code,value);
  293. #endif
  294.           error_exit(ERROR_BOUNDS);
  295.         }
  296.       else
  297.         {
  298.           CurrentState = Next;
  299.         }
  300.     }
  301.     }
  302.   if (code & 1)
  303.     {
  304.       Next = GetLeft(CurrentState,huff);
  305.  
  306.       if (Next != EmptyState)
  307.     {
  308.  
  309. #ifdef HUFF_DEBUG
  310.       fprintf(stderr,"Overflow on Huffman Table: Nonunique prefix(L).\n");
  311.       fprintf(stderr,"Length: %d   Code: %d|%x  Value: %d|%x\n",n,code,code,value,value);
  312. #endif
  313.       error_exit(ERROR_BOUNDS);
  314.     }
  315.       SetLeft(MakeHVal(value),CurrentState,huff);
  316.     }
  317.   else
  318.     {
  319.       Next = GetRight(CurrentState,huff);
  320.     
  321.       if (Next != EmptyState)
  322.     {
  323. #ifdef HUFF_DEBUG
  324.       fprintf(stderr,"Overflow on Huffman Table: Nonunique prefix(R).\n");
  325.       fprintf(stderr,"Length: %d   Code: %d|%x  Value: %d|%x\n",n,code,code,value,value);
  326. #endif
  327.       error_exit(ERROR_BOUNDS);
  328.     }
  329.       SetRight(MakeHVal(value),CurrentState,huff);
  330.     }
  331. }
  332.